home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / comm / tcp / AmigaTCP.lha / AmigaTCP / src / iproute.c < prev    next >
C/C++ Source or Header  |  1989-06-24  |  16KB  |  640 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include <stdio.h>
  5. #include "machdep.h"
  6. #include "mbuf.h"
  7. #include "internet.h"
  8. #include "timer.h"
  9. #include "netuser.h"
  10. #include "ip.h"
  11. #include "icmp.h"
  12. #include "iface.h"
  13. #ifdef    TRACE
  14. #include "trace.h"
  15. #endif
  16.  
  17. struct route *routes[32][NROUTE];    /* Routing table */
  18. struct route r_default;            /* Default route entry */
  19.  
  20. int32 ip_addr;
  21. struct ip_stats ip_stats;
  22.  
  23. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  24.  * coming or going, must pass.
  25.  *
  26.  * This router is a temporary hack, since it only does host-specific or
  27.  * default routing (no hierarchical routing yet).
  28.  *
  29.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  30.  * broadcast. The router will kick the packet upstairs regardless of the
  31.  * IP destination address.
  32.  */
  33. void
  34. ip_route(bp,rxbroadcast)
  35. struct mbuf *bp;
  36. char rxbroadcast;    /* True if packet had link broadcast address */
  37. {
  38.     register struct ip_header *ip;    /* IP header being processed */
  39.     int16 ip_len;            /* IP header length */
  40.     int16 buflen;            /* Length of mbuf */
  41.     int16 length;            /* Total datagram length */
  42.     int32 target;            /* Target IP address */
  43.     int32 gateway;            /* Gateway IP address */
  44.     register struct route *rp;    /* Route table entry */
  45.     struct route *rt_lookup();
  46.     int opi;            /* Index into options field */
  47.     int opt_len;            /* Length of current option */
  48.     int strict;            /* Strict source routing flag */
  49.     struct mbuf *sbp;        /* IP header for fragmenting */
  50.     int16 fl_offs;            /* fl_offs field of datagram */
  51.     int16 offset;            /* Offset of fragment */
  52.     char precedence;        /* Extracted from tos field */
  53.     char delay;
  54.     char throughput;
  55.     char reliability;
  56.  
  57.     ip_stats.total++;
  58.     buflen = len_mbuf(bp);
  59.     if(buflen < sizeof(struct ip_header)){
  60.         /* The packet is shorter than a legal IP header */
  61.         ip_stats.runt++;
  62.         free_p(bp);
  63.         return;
  64.     }
  65.     ip = (struct ip_header *)bp->data;
  66.     length = ntohs(ip->length);
  67.     if(buflen > length){
  68.         /* Packet has excess garbage (e.g., Ethernet padding); trim */
  69.         if(bp->next == NULLBUF){
  70.             /* One mbuf, just adjust count */
  71.             bp->cnt = length;
  72.         } else {
  73.             struct mbuf *nbp;
  74.             /* Copy to a new one */
  75.             nbp = copy_p(bp,length);
  76.             free((char *)bp);
  77.             bp = nbp;
  78.             ip = (struct ip_header *)bp->data;
  79.         }
  80.     }
  81.     ip_len = lonibble(ip->v_ihl) * sizeof(int32);
  82.     if(ip_len < sizeof(struct ip_header)){
  83.         /* The IP header length field is too small */
  84.         ip_stats.length++;
  85.         free_p(bp);
  86.         return;
  87.     }
  88.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  89.         /* Bad IP header checksum; discard */
  90.         ip_stats.checksum++;
  91.         free_p(bp);
  92.         return;
  93.     }
  94.     if(hinibble(ip->v_ihl) != IPVERSION){
  95.         /* We can't handle this version of IP */
  96.         ip_stats.version++;
  97.         free_p(bp);
  98.         return;
  99.     }
  100.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  101.     if(ntohl(ip->dest) == ip_addr || rxbroadcast){
  102. #ifdef    GWONLY
  103.     /* We're only a gateway, we have no host level protocols */
  104.         if(!rxbroadcast)
  105.             icmp_output(bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  106.         free_p(bp);
  107. #else
  108. #ifdef    TRACE
  109.         if(trace & TRACE_SELF && ntohl(ip->source) == ip_addr){
  110.             printf("loopback:\r\n");
  111.             if((trace & TRACE_HDR) > 2)
  112.                 ip_dump(bp);
  113.             if(trace & TRACE_DUMP)
  114.                 hexdump(bp);
  115.             fflush(stdout);
  116.         }
  117. #endif
  118.         ip_recv(bp,rxbroadcast);
  119. #endif
  120.         return;
  121.     }
  122.     /* If we get here, we must forward the packet.
  123.      * Process options, if any. Also compute length of secondary IP
  124.      * header in case fragmentation is needed later
  125.      */
  126.     strict = 0;
  127.     for(opi = sizeof(struct ip_header);opi < ip_len; opi += opt_len){
  128.         char *opt;    /* Points to current option */
  129.         int opt_type;    /* Type of current option */
  130.         int pointer;    /* Pointer field of current option */
  131.         int32 *addr;    /* Pointer to an IP address field in option */
  132.  
  133.         opt = (char *)ip + opi;
  134.         opt_type = opt[0] & OPT_NUMBER;
  135.  
  136.         /* Handle special 1-byte do-nothing options */
  137.         if(opt_type == IP_EOL)
  138.             break;        /* End of options list, we're done */
  139.         if(opt_type == IP_NOOP){
  140.             opt_len = 1;    /* No operation, skip to next option */
  141.             continue;
  142.         }
  143.         /* Other options have a length field */
  144.         opt_len = opt[1] & 0xff;
  145.  
  146.         /* Process options */
  147.         switch(opt_type){
  148.         case IP_SSROUTE:/* Strict source route & record route */
  149.             strict = 1;
  150.         case IP_LSROUTE:/* Loose source route & record route */
  151.             /* Source routes are ignored unless the datagram appears to
  152.              * be for us
  153.              */
  154.             if(ntohl(ip->dest) != ip_addr)
  155.                 continue;
  156.         case IP_RROUTE:    /* Record route */
  157.             pointer = (opt[2] & 0xff) - 1;
  158.             if(pointer + sizeof(int32) <= opt_len){
  159.                 /* Insert our address in the list */
  160.                 addr = (int32 *)&opt[pointer];
  161.                 if(opt_type != IP_RROUTE)
  162.                     /* Old value is next dest only for source routing */
  163.                     ip->dest = *addr;
  164.                 *addr = htonl(ip_addr);
  165.                 opt[2] += 4;
  166.             } else {
  167.                 /* Out of space; return a parameter problem and drop */
  168.                 union icmp_args icmp_args;
  169.  
  170.                 icmp_args.unused = 0;
  171.                 icmp_args.pointer = sizeof(struct ip_header) + opi;
  172.                 icmp_output(bp,PARAM_PROB,0,&icmp_args);
  173.                 free_p(bp);
  174.                 return;
  175.             }
  176.             break;
  177.         }
  178.     }
  179.     /* Decrement TTL and discard if zero */
  180.     if(--ip->ttl == 0){
  181.         /* Send ICMP "Time Exceeded" message */
  182.         icmp_output(bp,TIME_EXCEED,0,NULLICMP);
  183.         free_p(bp);
  184.         return;
  185.     }
  186.     /* Note this address may have been modified by source routing */
  187.     target = ntohl(ip->dest);
  188.  
  189.     /* Look up target address in routing table */
  190.     if((rp = rt_lookup(target)) == NULLROUTE){
  191.         /* No route exists, return unreachable message */
  192.         icmp_output(bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  193.         free_p(bp);
  194.         return;
  195.     }
  196.     /* Find gateway; zero gateway in routing table means "send direct" */
  197.     if(rp->gateway == (int32)0)
  198.         gateway = target;
  199.     else
  200.         gateway = rp->gateway;
  201.  
  202.     if(strict && gateway != target){
  203.         /* Strict source routing requires a direct entry */
  204.         icmp_output(bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  205.         free_p(bp);
  206.         return;
  207.     }
  208.     precedence = PREC(ip->tos);
  209.     delay = ip->tos & DELAY;
  210.     throughput = ip->tos & THRUPUT;
  211.     reliability = ip->tos & RELIABILITY;
  212.  
  213.     if(length <= rp->interface->mtu){
  214.         /* Datagram smaller than interface MTU; send normally */
  215.         /* Recompute header checksum */
  216.         ip->checksum = 0;
  217.         ip->checksum = cksum(NULLHEADER,bp,ip_len);
  218.         (*rp->interface->send)(bp,rp->interface,gateway,
  219.             precedence,delay,throughput,reliability);
  220.         return;
  221.     }
  222.     /* Fragmentation needed */
  223.     fl_offs = ntohs(ip->fl_offs);
  224.     if(fl_offs & DF){
  225.         /* Don't Fragment set; return ICMP message and drop */
  226.         icmp_output(bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  227.         free_p(bp);
  228.         return;
  229.     }
  230.     /* Create copy of IP header for each fragment */
  231.     sbp = copy_p(bp,ip_len);
  232.     pullup(&bp,NULLCHAR,ip_len);
  233.     length -= ip_len;
  234.  
  235.     /* Create fragments */
  236.     offset = (fl_offs & F_OFFSET) << 3;
  237.     while(length != 0){
  238.         int16 fragsize;        /* Size of this fragment's data */
  239.         struct mbuf *f_header;    /* Header portion of fragment */
  240.         struct ip_header *fip;    /* IP header */
  241.         struct mbuf *f_data;    /* Data portion of fragment */
  242.  
  243.         f_header = copy_p(sbp,ip_len);
  244.         fip = (struct ip_header *)f_header->data;
  245.         fip->fl_offs = htons(offset >> 3);
  246.         if(length + ip_len <= rp->interface->mtu){
  247.             /* Last fragment; send all that remains */
  248.             fragsize = length;
  249.         } else {
  250.             /* More to come, so send multiple of 8 bytes */
  251.             fragsize = (rp->interface->mtu - ip_len) & 0xfff8;
  252.             fip->fl_offs |= htons(MF);
  253.         }
  254.         fip->length = htons(fragsize + ip_len);
  255.         /* Recompute header checksum */
  256.         fip->checksum = 0;
  257.         fip->checksum = cksum(NULLHEADER,f_header,ip_len);
  258.  
  259.         /* Extract portion of data and link in */
  260.         f_data = copy_p(bp,fragsize);
  261.         pullup(&bp,NULLCHAR,fragsize);
  262.         f_header->next = f_data;
  263.  
  264.         (*rp->interface->send)(f_header,rp->interface,gateway,
  265.             precedence,delay,throughput,reliability);
  266.         offset += fragsize;
  267.         length -= fragsize;
  268.     }
  269.     free_p(sbp);
  270. }
  271.  
  272. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  273. int
  274. rt_add(target,bits,gateway,metric,interface)
  275. int32 target;    /* Target IP address prefix */
  276. unsigned bits;    /* Size of target address prefix in bits (0-32) */
  277. int32 gateway;
  278. int metric;
  279. struct interface *interface;
  280. {
  281.     struct route *rp,**hp,*rt_lookup();
  282.     int16 hash_ip(),i;
  283.     char *malloc();
  284.  
  285.     if(interface == NULLIF)
  286.         return -1;
  287.  
  288.     /* Zero bits refers to the default route */
  289.     if(bits == 0){
  290.         rp = &r_default;
  291.     } else {
  292.         if(bits > 32)
  293.             bits = 32;
  294.  
  295.         /* Mask off don't-care bits */
  296.         for(i=31;i >= bits;i--)
  297.             target &= ~(0x80000000 >> i);
  298.  
  299.         /* Search appropriate chain for existing entry */
  300.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  301.             if(rp->target == target)
  302.                 break;
  303.         }
  304.     }
  305.     if(rp == NULLROUTE){
  306.         /* The target is not already in the table, so create a new
  307.          * entry and put it in.
  308.          */
  309.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  310.             return -1;    /* No space */
  311.         /* Insert at head of table */
  312.         rp->prev = NULLROUTE;
  313.         hp = &routes[bits-1][hash_ip(target)];
  314.         rp->next = *hp;
  315.         if(rp->next != NULLROUTE)
  316.             rp->next->prev = rp;
  317.         *hp = rp;
  318.     }
  319.     rp->target = target;
  320.     rp->gateway = gateway;
  321.     rp->metric = metric;
  322.     rp->interface = interface;
  323.     return 0;
  324. }
  325.  
  326. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  327.  * if entry was not in table.
  328.  */
  329. int
  330. rt_drop(target,bits)
  331. int32 target;
  332. unsigned bits;
  333. {
  334.     register struct route *rp;
  335.     struct route *rt_lookup();
  336.     unsigned i;
  337.  
  338.     if(bits == 0){
  339.         /* Nail the default entry */
  340.         r_default.interface = NULLIF;
  341.         return 0;
  342.     }
  343.     if(bits > 32)
  344.         bits = 32;
  345.  
  346.     /* Mask off don't-care bits */
  347.     for(i=31;i > bits;i--)
  348.         target &= ~(0x80000000 >> i);
  349.  
  350.     /* Search appropriate chain for existing entry */
  351.     for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  352.         if(rp->target == target)
  353.             break;
  354.     }
  355.     if(rp == NULLROUTE)
  356.         return -1;    /* Not in table */
  357.  
  358.     if(rp->next != NULLROUTE)
  359.         rp->next->prev = rp->prev;
  360.     if(rp->prev != NULLROUTE)
  361.         rp->prev->next = rp->next;
  362.     else
  363.         routes[bits-1][hash_ip(target)] = rp->next;
  364.  
  365.     free((char *)rp);
  366.     return 0;
  367. }
  368.  
  369. /* Compute hash function on IP address */
  370. static int16
  371. hash_ip(addr)
  372. register int32 addr;
  373. {
  374.     register int16 ret;
  375.  
  376.     ret = hiword(addr);
  377.     ret ^= loword(addr);
  378.     ret %= NROUTE;
  379.     return ret;
  380. }
  381. #ifndef    GWONLY
  382. /* Given an IP address, return the MTU of the local interface used to
  383.  * reach that destination. This is used by TCP to avoid local fragmentation
  384.  */
  385. int16
  386. ip_mtu(addr)
  387. int32 addr;
  388. {
  389.     register struct route *rp;
  390.     struct route *rt_lookup();
  391.  
  392.     rp = rt_lookup(addr);
  393.     if(rp != NULLROUTE && rp->interface != NULLIF)
  394.         return rp->interface->mtu;
  395.     else
  396.         return 0;
  397. }
  398. #endif
  399. /* Look up target in hash table, matching the entry having the largest number
  400.  * of leading bits in common. Return default route if not found;
  401.  * if default route not set, return NULLROUTE
  402.  */
  403. static struct route *
  404. rt_lookup(target)
  405. int32 target;
  406. {
  407.     register struct route *rp;
  408.     int16 hash_ip();
  409.     unsigned bits;
  410.  
  411.     for(bits = 32;bits != 0; bits--){
  412.         if(bits != 32)
  413.             target &= ~(0x80000000 >> bits);
  414.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  415.             if(rp->target == target)
  416.                 return rp;
  417.         }
  418.     }
  419.     if(r_default.interface != NULLIF)
  420.         return &r_default;
  421.     else
  422.         return NULLROUTE;
  423. }
  424. /* Internet checksum routines
  425.  * Improved portability courtesy Rick Spanbauer, WB2CFV
  426.  */
  427. #define SLOWCHECK
  428. #ifdef SLOWCHECK
  429. /*
  430.  * Word aligned linear buffer checksum routine.  Called from mbuf checksum
  431.  * routine with simple args.  Intent is that this routine may be replaced
  432.  * by assembly language routine for speed if so desired.
  433.  */
  434. static int16
  435. lcsum(sum, wp, len)
  436. register int32 sum;
  437. register int16 *wp;
  438. int16 len;
  439. {
  440.     register int16 csum;
  441.  
  442.     while(len-- != 0)
  443.         sum += *wp++;
  444.     while((csum = sum >> 16) != 0)
  445.         sum = csum + (sum & 0xffff);
  446.     return sum & 0xffff;
  447. }
  448. #endif SLOWCHECK
  449.  
  450. /* Perform end-around-carry adjustment */
  451. static int16
  452. eac(sum)
  453. register int32 sum;    /* Carries in high order 16 bits */
  454. {
  455.     register int16 csum;
  456.  
  457.     while((csum = sum >> 16) != 0)
  458.         sum = csum + (sum & 0xffff);
  459.     return sum;    /* Chops to 16 bits */
  460. }
  461. /* Checksum a mbuf chain, with optional pseudo-header */
  462. int16
  463. cksum(ph,m,len)
  464. struct pseudo_header *ph;
  465. register struct mbuf *m;
  466. int16 len;
  467. {
  468.     register unsigned int cnt, total;
  469.     register int32 sum, csum;
  470.     register unsigned char *up;
  471.  
  472.     sum = 0l;
  473.  
  474.     /* Sum pseudo-header, if present */
  475.     if(ph != NULLHEADER){
  476.         sum = hiword(ph->source);
  477.         sum += loword(ph->source);
  478.         sum += hiword(ph->dest);
  479.         sum += loword(ph->dest);
  480.         sum += ph->protocol & 0xff;
  481.         sum += ph->length;
  482.         /* Swapping the sum is equivalent to summing the swapped
  483.          * elements, but faster. Do end-around-carry first.
  484.          */
  485.         sum = htons(eac(sum));
  486.     }
  487.     /* Now do each mbuf on the chain */
  488.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  489.         cnt = min(m->cnt, len - total);
  490.         up = (unsigned char *)m->data;
  491.  
  492.         /* Handle odd leading byte */
  493.         if(((long)up) & 1){
  494.             csum = (int16)ntohs(*up++);
  495.             cnt--;
  496.         } else
  497.             csum = 0;
  498.  
  499.         /* Handle odd trailing byte */
  500.         if(cnt & 1)
  501.             csum += (int16)ntohs(up[--cnt]<<8);
  502.  
  503.         if(cnt != 0){
  504.             /* Have the primitive checksumming routine do most of
  505.              * the work. At this point, up is guaranteed to be on
  506.              * a short boundary and cnt is guaranteed to be even
  507.              */
  508.             csum = lcsum(csum, (unsigned short *)up, cnt >> 1);
  509.         }
  510.         /* If the mbuf we just did wasn't on a word boundary within
  511.          * the whole packet, then byteswap the checksum for this mbuf
  512.          */
  513.         if((total&1) ^ (((long)m->data)&1)){
  514.             csum = eac(csum);
  515.             csum = (csum >> 8) + ((csum&0xff) << 8);
  516.         }
  517.         sum += csum;
  518.         total += m->cnt;
  519.     } 
  520.     /* Do final end-around carry, complement and return */
  521.     return ~eac(sum) & 0xffff;
  522. }
  523. #ifdef    TRACE
  524. #include "trace.h"
  525.  
  526. void
  527. ip_dump(bp)
  528. struct mbuf *bp;
  529. {
  530.     void tcp_dump(),udp_dump(),icmp_dump();
  531.     register struct ip_header *ip;
  532.     int32 source,dest;
  533.     int16 ip_len;
  534.     int16 length;
  535.     struct mbuf *tbp;
  536.     int16 offset;
  537.     int i;
  538.     int check;
  539.     char tmpbuf;    
  540.  
  541.     if(bp == NULLBUF)
  542.         return;    
  543.  
  544.     /* If packet isn't in a single buffer, make a temporary copy and
  545.      * note the fact so we free it later
  546.      */
  547.     if(bp->next != NULLBUF){
  548.         bp = copy_p(bp,len_mbuf(bp));
  549.         tmpbuf = 1;
  550.     } else
  551.         tmpbuf = 0;
  552.  
  553.     ip = (struct ip_header *)bp->data;
  554.     ip_len = lonibble(ip->v_ihl) * sizeof(int32);
  555.     length = ntohs(ip->length);
  556.     offset = (ntohs(ip->fl_offs) & F_OFFSET) << 3 ;
  557.     source = ntohl(ip->source);
  558.     dest = ntohl(ip->dest);
  559.     printf("IP: %s",inet_ntoa(source));
  560.     printf("->%s len %u ihl %u ttl %u prot %u",
  561.         inet_ntoa(dest),length,ip_len,ip->ttl & 0xff,
  562.         ip->protocol & 0xff);
  563.  
  564.     if(ip->tos != 0)
  565.         printf(" tos %u",ip->tos);
  566.     if(offset != 0 || (ntohs(ip->fl_offs) & MF))
  567.         printf(" id %u offs %u",ntohs(ip->id),offset);
  568.  
  569.     if(ntohs(ip->fl_offs) & DF)
  570.         printf(" DF");
  571.     if(ntohs(ip->fl_offs) & MF){
  572.         printf(" MF");
  573.         check = 0;    /* Bypass host-level checksum verify */
  574.     } else {
  575.         check = 1;
  576.     }
  577.  
  578.     if((i = cksum(NULLHEADER,bp,ip_len)) != 0)
  579.         printf(" CHECKSUM ERROR (%u)",i);
  580.     printf("\r\n");
  581.  
  582.     if((trace & TRACE_HDR) > 3){
  583.         if(offset == 0){
  584.             dup_p(&tbp,bp,ip_len,length - ip_len);
  585.             switch(ip->protocol & 0xff){
  586.             case TCP_PTCL:
  587.                 tcp_dump(tbp,source,dest,check);
  588.                 break;
  589.             case UDP_PTCL:
  590.                 udp_dump(tbp,source,dest,check);
  591.                 break;
  592.             case ICMP_PTCL:
  593.                 icmp_dump(tbp,source,dest,check);
  594.                 break;
  595.             }
  596.             free_p(tbp);
  597.         }
  598.     }
  599.     if(tmpbuf)
  600.         free_p(bp);
  601.     fflush(stdout);
  602. }
  603. /* Dump IP routing table
  604.  * Dest              Length    Interface    Gateway          Metric
  605.  * 192.001.002.003   32        sl0          192.002.003.004       4
  606.  */
  607. int
  608. dumproute()
  609. {
  610.     register unsigned int i,bits;
  611.     register struct route *rp;
  612.  
  613.     printf("Dest              Length    Interface    Gateway          Metric\r\n");
  614.     if(r_default.interface != NULLIF){
  615.         printf("default           0         %-13s",
  616.          r_default.interface->name);
  617.         if(r_default.gateway != 0)
  618.             printf("%-17s",inet_ntoa(r_default.gateway));
  619.         else
  620.             printf("%-17s","");
  621.         printf("%6u\r\n",r_default.metric);
  622.     }
  623.     for(bits=1;bits<=32;bits++){
  624.         for(i=0;i<NROUTE;i++){
  625.             for(rp = routes[bits-1][i];rp != NULLROUTE;rp = rp->next){
  626.                 printf("%-18s",inet_ntoa(rp->target));
  627.                 printf("%-10u",bits);
  628.                 printf("%-13s",rp->interface->name);
  629.                 if(rp->gateway != 0)
  630.                     printf("%-17s",inet_ntoa(rp->gateway));
  631.                 else
  632.                     printf("%-17s","");
  633.                 printf("%6u\r\n",rp->metric);
  634.             }
  635.         }
  636.     }
  637.     return 0;
  638. }
  639. #endif
  640.